GCD Property of the Division Algorithm
For integers \(a\) and \(b\) with \(b \neq 0\), if the division algorithm for integers is applied as follows
then \(\gcd(a, b) = \gcd(b, r)\).
Proof
To prove the above, we proceed by showing independently that \(\gcd(a, b) \leq \gcd(b, r)\) and \(\gcd(a, b) \geq \gcd(b, r)\).
Let \(g_{1} = \gcd(a, b)\). By definition \(g_{1} \mid a\) and \(g_{1} \mid b\). From this, \(g_{1} \mid bq\) and therefore \(g_{1} \mid bq - a = r\). This means that \(g_{1}\) is a common divisor of \(b\) and \(r\), but not necessarily the greatest. Hence
We then make a similar argument in the opposite direction. Let \(g_{2} = \gcd(b, r)\). By definition \(g_{2} \mid b\) and \(g_{2} \mid r\). From this, \(g_{2} \mid bq\) and therefore \(g_{2} \mid bq + r = a\). This means that \(g_{2}\) is a common divisor of \(a\) and \(b\), but not necessarily the greatest. Hence:
Combining the above results proves equality: